Hashtable源码分析

HashTable同HashMap类似，它也是一种散列表，用于存储键值对。本篇将对HashTable源码进行分析。

继承关系和结构

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    private transient Entry<K,V>[] table;
    private transient int count;
    private int threshold;
    private float loadFactor;

    ……
}

private static class Entry<K,V> implements Map.Entry<K,V> {
    int hash;
    final K key;
    V value;
    Entry<K,V> next;
    ……
}

Hashtable不同于HashMap继承自Dictionary抽象类，但相同的继承了Map,Cloneable,Serializable接口。成员类似于HashMap,table为散列表，count为元素个数，threshold为阈值，当容量大于等于阈值时扩容，loadFactor为加载因子用于计算阈值。Entry结构和HashMap一样，用于存储键值对。

构造方法

public Hashtable() {
    this(11, 0.75f);
}

public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);

    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    initHashSeedAsNeeded(initialCapacity);
}

构造方法默认大小为11 ，加载因子为0.75，阈值= 11*0.75 = 8

添加元素

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

    modCount++;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();
        tab = table;
        hash = hash(key);
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    Entry<K,V> e = tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
    return null;
}

private int hash(Object k) {
    // hashSeed will be zero if alternative hashing is disabled.
    return hashSeed ^ k.hashCode();
}

添加的逻辑首先判断value是否为null，同时通过hash计算key的hash值，在hash方法中同样可以看到key值不能为你null，否则同样抛出异常。这点和HashMap不一样，计算完hash后，计算散列表的索引位置，然后遍历bucket，找到对应的key后，更新value值即可，否则判断count是否大于等于阈值，如果是则需要rehash，这个就是扩容的过程，最后为这个新的键值对创建Entry，并放在bucket的头部。

需要注意的是：put方法被synchronized修饰，即它是线程安全的。

移除元素

public synchronized V remove(Object key) {
    Entry tab[] = table;
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}

移除元素的过程也很简单，同样是通过hash值计算索引后取到对应的bucket，然后遍历找到对应的key值后从bucket删除即可。类似的remove也是线程安全的。

扩容

 protected void rehash() {
    int oldCapacity = table.length;
    Entry<K,V>[] oldMap = table;

    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<K,V>[] newMap = new Entry[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    boolean rehash = initHashSeedAsNeeded(newCapacity);

    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            if (rehash) {
                e.hash = hash(e.key);
            }
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = newMap[index];
            newMap[index] = e;
        }
    }
}

Hashtable的扩容操作基本和HashMap是相同的，只不过新的容量=(oldCapacity << 1) + 1，而HashMap中是旧容量的2倍。而且MAX_ARRAY_SIZE 为 Integer.MAX_VALUE - 8.

遍历

Iterator<Map.Entry<K,V>> i = entrySet().iterator();
while (i.hasNext()) {
    Map.Entry<K,V> e = i.next();
}

通过迭代器迭代遍历的一般形式，当然也可以通过keySet,进行迭代。这里我们看看entrySet的实现即可。

public Set<Map.Entry<K,V>> entrySet() {
    if (entrySet==null)
        entrySet = Collections.synchronizedSet(new EntrySet(), this);
    return entrySet;
}

entrySet会创建一个EntrySet对象

private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return getIterator(ENTRIES);
    }
    ……
}

iterator会通过getIterator返回一个迭代器

private <T> Enumeration<T> getEnumeration(int type) {
    if (count == 0) {
        return Collections.emptyEnumeration();
    } else {
        return new Enumerator<>(type, false);
    }
}

private <T> Iterator<T> getIterator(int type) {
    if (count == 0) {
        return Collections.emptyIterator();
    } else {
        return new Enumerator<>(type, true);
    }
}

Hashtable支持Enumberation和Iterator的遍历方式，Enumberation是比较旧的遍历方式，Hashtable中使用Enumberation是历史问题，同时Hashtable支持Iterator,这两种不同的迭代方式都是通过Enumberator实现的。实际是使用了标记做区分，false为Enumberation，true为Iterator.

private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
    Entry[] table = Hashtable.this.table;
    int index = table.length;
    Entry<K,V> entry = null;
    Entry<K,V> lastReturned = null;
    int type;

    boolean iterator;
    protected int expectedModCount = modCount;

    Enumerator(int type, boolean iterator) {
        this.type = type;
        this.iterator = iterator;
    }

    ……
    // Iterator methods
    public boolean hasNext() {
        return hasMoreElements();
    }

    public T next() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        return nextElement();
    }

    public void remove() {
        if (!iterator)
            throw new UnsupportedOperationException();
        if (lastReturned == null)
            throw new IllegalStateException("Hashtable Enumerator");
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();

        synchronized(Hashtable.this) {
            Entry[] tab = Hashtable.this.table;
            int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;

            for (Entry<K,V> e = tab[index], prev = null; e != null;
                    prev = e, e = e.next) {
                if (e == lastReturned) {
                    modCount++;
                    expectedModCount++;
                    if (prev == null)
                        tab[index] = e.next;
                    else
                        prev.next = e.next;
                    count--;
                    lastReturned = null;
                    return;
                }
            }
            throw new ConcurrentModificationException();
        }
    }
}

可以看到对于Enumberation是不支持remove的，而Iterator支持remove。next方法会取出迭代器下一个可用的元素，它是通过nextElement实现的，hasNext则是判断迭代器中还有没有可用的元素，它通过hasMoreElements实现的。下面我们具体分析

public boolean hasMoreElements() {
    Entry<K,V> e = entry;
    int i = index;
    Entry[] t = table;
    /* Use locals for faster loop iteration */
    while (e == null && i > 0) {
        e = t[--i];
    }
    entry = e;
    index = i;
    return e != null;
}

初始情况下entry为null,index为table.length,可以看出hasMoreElements从散列表的后向开始遍历，判断当前entry是否为null，为null则切换bucket继续查找，不为null返回true.

public T nextElement() {
    Entry<K,V> et = entry;
    int i = index;
    Entry[] t = table;
    /* Use locals for faster loop iteration */
    while (et == null && i > 0) {
        et = t[--i];
    }
    entry = et;
    index = i;
    if (et != null) {
        Entry<K,V> e = lastReturned = entry;
        entry = e.next;
        return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
    }
    throw new NoSuchElementException("Hashtable Enumerator");
}

nextElement用来获取可用的元素，这里可以获取到可用元素的条件是hasMoreElements返回true，即entry不为null，获取到后根据指定的type分别取到key，value或者entry返回，并且将entry赋为e.next即下个Entry。